(1) Field of the Invention
This invention relates to a technique for estimating the displacement and/or velocity of objects in a picture using a transform domain representation of the picture, and a related technique for encoding the transform coefficient of the picture using motion compensation.
(2) Description of the Prior Art
In various prior art video encoding systems, it has been found advantageous to partition individual frames of video data into blocks or groups of picture elements, and to perform a two-dimensional, generally linear transformation of each block so as to generate a set of transform coefficients. These coefficients are then used for prediction purposes, i.e., the transform coefficients of a given block of pels in the previous (reference) frame are used to predict the corresponding coefficient values for the present frame. If the prediction error exceeds a threshold, the error value is quantized and encoded for transmission. If the threshold is not exceeded, it is assumed that the inaccuracy caused by not encoding the error value is tolerable. The quantized error values add, as correction terms, to the predicted transform coefficients. In the decoder, the coefficients are applied to an inverse transform circuit to recover a replica of the original video signal.
Interframe hybrid transform/DPCM coders of the type described achieve compression by the redundancy reduction implicit in the prediction process and also by the fact that some coefficients can be reproduced with low precision (or totally omitted) without visibly degrading the reconstructed image. An advantage of interframe hybrid transform/DPCM coding over conventional three-dimensional block interframe coding of the type described in S. C. Knauer, "Real-Time Video Compression Algorithm for Hadamard Transform Processing", Proceedings of SPIE, Vol. 66, August 1975, pp. 58-69, is that the hybrid coder requires only a single frame of storage, while the conventional transform coder requires several frame stores. Different transformation techniques have been successfully employed, including cosine and Hadamard transforms. See, for example, C. Reader, "Orthogonal Transform Coding of Still and Moving Pictures", Ph.D. Dissertation, The University of Sussex, United Kingdom, 1974; J. A. Roese, W. K. Pratt and G. S. Robinson, "Interframe Cosine Transform Image Coding", IEEE Transactions on Communications, COM-25, No. 11, November 1977, pp. 1329-1339; and H. W. Jones, "A Conditional Replenishment Hadamard Video Compressor", SPIE, Vol. 119, Applications of Digital Image Processing, 1977, pp. 91-98. Haar, Slant and Karhunen-Loeve transforms have also been used.
While significant redundancy reduction is achieved with interframe hybrid transform coders, the availability of inexpensive processing circuitry makes further efficiency improvement possible, and this indeed is the broad object of the present invention. Naturally, it is desirable that the encoded signal faithfully reproduce the original input, when decoded, and that storage requirements (as opposed to processing circuits) be kept to a minimum.